#include <stdio.h>

void merge(double *a, int p, int q, int r)
{
  int i, j, k;
  int n1 = q - p + 1;
  int n2 = r - q;
  double left[n1], right[n2];

  for (i = 0; i < n1; i++)
    left[i] = a[p + i];
  for (i = 0; i < n2; i++)
    right[i] = a[q + 1 + i];
  for (i = j = 0, k = p; k <= r; k++){
    if (i == n1)
      while (j < n2)
	a[k++] = right[j++];
    else if (j == n2)
      while (i < n1)
	a[k++] = left[i++];
    else
      a[k] = (left[i] < right[j]) ? left[i++] : right[j++];
  }
}

void merge_sort(double *a, int p, int r)
{
  int q;
  if (p < r) {
    q = (p + r) / 2;
    merge_sort(a, p, q);
    merge_sort(a, q + 1, r);
    merge(a, p, q, r);
  }
}
